package btree;

import java.util.LinkedList;

public class BTreeUtils {

    /**
     * 递归方法先序遍历二叉树
     *
     * @param root
     * @param visitor
     */
    public static void preorderTraverse(BTree root, Visitor visitor) {
        if (root != null) {
            visitor.visit(root);
            preorderTraverse(root.getLeftChild(), visitor);
            preorderTraverse(root.getRightChild(), visitor);
        }
    }

    /**
     * 一种先序遍历二叉树的非递归方法（利用辅助栈和先序遍历的特点）
     *
     * @param root
     * @param visitor
     */
    public static void preorderTraverseByStack(BTree root, Visitor visitor) {
        if (root != null) {
            LinkedList<BTree> stack = new LinkedList<BTree>();
            BTree p = root;
            while (!stack.isEmpty() || p != null) {
                while (p != null) {
                    visitor.visit(p);
                    stack.addLast(p);
                    p = p.getLeftChild();
                }
                if (!stack.isEmpty()) {
                    BTree last = stack.removeLast();
                    p = last.getRightChild();
                }
            }
        }
    }

    /**
     * 递归方法中序遍历二叉树
     *
     * @param root
     * @param visitor
     */
    public static void inorderTraverse(BTree root, Visitor visitor) {
        if (root != null) {
            inorderTraverse(root.getLeftChild(), visitor);
            visitor.visit(root);
            inorderTraverse(root.getRightChild(), visitor);
        }
    }

    /**
     * 非递归方法（利用辅助栈和中序遍历的特点）中序遍历二叉树
     *
     * @param root
     * @param visitor
     */
    public static void inorderTraverseByStack(BTree root, Visitor visitor) {
        LinkedList<BTree> stack = new LinkedList<BTree>();
        if (root != null) {
            BTree p = root;
            while (!stack.isEmpty() || p != null) {
                while (p != null) {
                    stack.addLast(p);
                    p = p.getLeftChild();
                }
                if (!stack.isEmpty()) {
                    p = stack.removeLast();
                    visitor.visit(p);
                    p = p.getRightChild();
                }
            }
        }
    }


    /**
     * 递归方法后序遍历二叉树
     *
     * @param root
     * @param visitor
     */
    public static void postorderTraverse(BTree root, Visitor visitor) {
        if (root != null) {
            postorderTraverse(root.getLeftChild(), visitor);
            postorderTraverse(root.getRightChild(), visitor);
            visitor.visit(root);
        }
    }

    /**
     * 非递归方法（利用辅助栈）后序遍历二叉树
     *
     * @param root
     * @param visitor
     */
    public static void postorderTraverseByStack(BTree root, Visitor visitor) {
        if (root != null) {
            LinkedList<StateNode> stack = new LinkedList<StateNode>();
            stack.addLast(new StateNode(root, false));
            while (!stack.isEmpty()) {
                StateNode top = stack.removeLast();
                if (top.flag) {
                    visitor.visit(top.node);
                    ;
                } else {
                    stack.addLast(new StateNode(top.node, true));
                    if (top.node.getRightChild() != null) {
                        stack.addLast(new StateNode(top.node.getRightChild(), false));
                    }
                    if (top.node.getLeftChild() != null) {
                        stack.addLast(new StateNode(top.node.getLeftChild(), false));
                    }
                }
            }
        }
    }

    /**
     * 带状态的结点类，用于辅助二叉树的遍历
     *
     * @author zj
     */
    static class StateNode {
        public BTree node;
        public boolean flag;

        public StateNode(BTree node, boolean flag) {
            this.flag = flag;
            this.node = node;
        }
    }
}
